// 给定一个升序数组nums和一个目标值target，找出给定目标值在数组中的开始位置和结束位置，要求使用时间复杂度为O(logn)
// 思路：二分查找思路，left。right指针，左闭右闭
// 需要两次查找，第一次查找最左边的target位置，第二次查找最右边的target位置
// 第一次查找需要移动left指针（即使右指针和target相等）
// 第二次查找需要移动right指针（即使左指针和target相等）
// 时间复杂度：O(logn)
// 空间复杂度：O(1)

function searchRange(arr, target) {
    let left = 0
    let right = arr.length - 1
    let ans = [-1, -1]
    while (left < right) {
        let mid = Math.floor((right - left) / 2) + left
        if (arr[mid] < target) {
            left = mid + 1
        } else {
            right = mid
        }
    }
    if (arr[left] !== target) {
        return ans
    }
    ans[0] = left
    left = 0
    right = arr.length - 1
    while (left < right) {
        let mid = Math.ceil((right - left) / 2) + left
        if (arr[mid] > target) {
            right = mid - 1
        } else {
            left = mid
        }
    }
    if (arr[right] === target) {
        ans[1] = right
    }
    
    return ans
}


let arr = [1, 2, 2, 3, 3, 3, 3, 4]
console.log(searchRange(arr,4));
let arr2 = [3]
console.log(searchRange(arr2,4));